home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1993 / Internet Info CD-ROM (Walnut Creek) (1993).iso / standards / misc / FileTransfer / XMODEM-CRC.NOTE.1 < prev    next >
Encoding:
Text File  |  1993-07-15  |  8.5 KB  |  212 lines
  1.                    Calculating the XMODEM CRC
  2.                          J. LeVan, Ph.D.
  3.  
  4. Introduction:
  5.      I have been in the process of developing a terminal emulator
  6. program for my home computer.  I was very unhappy with the Xmodem
  7. transfer  rate,  especially at high modem speeds.   The  checksum
  8. method  is clearly faster,  but cannot catch communication errors
  9. as  effectively.   The CRC method has an upper end throughput  of
  10. 500 bytes per second.
  11.  
  12.      I place a help call on CompuServe and receive an  intriquing
  13. response  from Bela Lubkin.   The algorithm he suggested appeared
  14. to be much quicker than the classical bit shift method.   It  was
  15. not at all clear to me how the algorithm worked.   The purpose of
  16. this  note  is  an  explanation of how and  why  a  table  lookup
  17. algorithm can work.
  18.  
  19.      Throughout  this note,  I will use "effective throughput" to
  20. mean:
  21.   (SizeOfPacket * NumberOfPackets)/(TimeOfEot - TimeOfInitialSOH)
  22. All source code will be in C.  These programs were written to run
  23. on an Apple MacIntosh, which is equipped with a high speed serial
  24. port.
  25.      Below  is  the  standard  bit  shift  and  occasionally  XOR
  26. algorithm.   The condition for doing the XOR is simply, if a 1 is
  27. going  to be shifted out of the sign bit then shift and  XOR  the
  28. old  CRC  with  the  generator.   Note that  the  inner  loop  is
  29. performed exactly eight times.
  30. ________________________________________________________________
  31. ___Fig.1: Bit Shift CRC_________________________________________
  32.  
  33. unsigned short ComputeCrc(crc,bufptr,len)
  34. register unsigned short crc;   /* unsigned shorts are 16 bits */
  35. register char *bufptr;
  36. register short len;
  37. {
  38.      register int   i;
  39.      while (len--) {           /* calculate CRC from end to start*/
  40.           crc ^= (unsigned short) (*bufptr++)<<8;
  41.           for ( i=0 ; i<8 ; ++i ) {
  42.                if (crc & 0x8000)
  43.                     crc = (crc << 1) ^ 0x1021;
  44.                else
  45.                     crc <<= 1;
  46.           }
  47.      }
  48.      return(crc);
  49. }
  50. ________________________________________________________________
  51.  
  52.      After  exactly eight shifts,  there will be no carries  from
  53. the low byte out of the top of the high byte.  This leads us to a
  54. critical observation:
  55.  
  56. Ob  1:  Whether  or  not an XOR is done with the CRC  does  *not*
  57. depend on the low byte of the CRC.
  58.  
  59.      Let A,  B,  and C be sixteen bit unsigned quantities.  We'll
  60. use the standard C notation for XOR,  a carat (^).  The following
  61. mathematical properties hold.
  62.  
  63. Ob 2:  XOR is Associative and Commutative.  I.e: For any choice
  64. of A, B and C; these equations will always hold true:
  65.      A^B = B^A                                    (1)
  66.      (A^B)^C = A^(B^C)                            (2)
  67.  
  68.      Likewize,  using  the standard C notation for a  left  shift
  69. ( A<<B means A shifted left B times ),  it can be shown that left
  70. shift is distributive over XOR.
  71.  
  72. Ob 3:  Left shift distributes over XOR.  I.e: For any choice of A
  73. and B; this equation will always hold true:
  74.      (A^B)<<1 = (A<<1) ^ (B<<1)                   (3)
  75.  
  76.      Now  take  a close look at the inner loop of the  ComputeCrc
  77. algorithm.   First  decompose the variable 'crc' into two  parts,
  78. 'crch' and 'crcl'.   The variable 'crch' is simply the high  byte
  79. of  'crc'  with the low byte changed to all  zeroes.   Similarly,
  80. 'crcl' is the low byte of 'crc',  with zeroes in the high half of
  81. that word.  To create 'crc' from 'crch' and 'crcl' we can use:
  82.  
  83.      crc = crch ^ crcl
  84.  
  85. The first pass through the loop yields:
  86.  
  87.      crc = ((crch ^ crcl)<<1) ^ P1
  88.  
  89. wherein P1 is either 0 or 0x1021. After two iterations we have:
  90.  
  91.      crc = {[ ((crch^crcl)<<1) ^ P1] << 1} ^ P2
  92. or:
  93.      crc = (crch << 2) ^ (crcl << 2) ^ (P2 << 1) ^ P2
  94.  
  95. wherein P2 is either 0 or 0x1021.  Looking ahead we can write the
  96. equation for crc after eight iterations:
  97.  
  98.      crc = (crch << 8) ^ (crcl << 8) ^ ((P1<<7) ^ (P2<<6) ^..^ P8)
  99.  
  100.      The term (crch<<8) vanishes, and (crcl<<8) is easy enough to
  101. compute  so the only question remaining is how we  can  calculate
  102. the last term.  Observation one tells us that the third term only
  103. depends  on  the initial value of crch.   This means that we  can
  104. compute  the third term by computing all possible values  in  the
  105. inner  loop  for  crc = 0x0000 to 0xFF00 stepping  by  0x100  and
  106. storing  the  values  in an array  CrcTable,  indexed  by  values
  107. running  from 0x00 to 0xFF.   This is exactly the function of the
  108. algorithm presented below:
  109.  
  110.  
  111. ________________________________________________________________
  112. ___Fig.2: Table lookup CRC______________________________________
  113.  
  114.  
  115. unsigned short CrcTable[256];   /* declaration for the table */
  116.  
  117. InitCrcTable()
  118. /* this routine calls ComputeCrc, defined in Fig.1 */
  119. {
  120.      int count;
  121.      char zero;
  122.      zero=0;
  123.      for ( count=0 ; count<256 ; count++ )
  124.           CrcTable[count] = ComputeCrc(count<<8,&zero,1);
  125. }
  126.  
  127. unsigned short TableCrc(crc,bufptr,len)
  128. register unsigned short crc;
  129. register unsigned char *bufptr;
  130. register short len;
  131. {
  132.      while (len--)
  133.           crc = CrcTable[crc >> 8^(*bufptr++)] ^ crc<<8;
  134.      return(crc);
  135. }
  136.  
  137. ________________________________________________________________
  138.  
  139. Thus our third term is found by:
  140.  
  141.      ((P1<<7) ^ (P2<<6) ^ ... ^ P8) = CrcTable[crch>>8]
  142. the final crc is caluclated by:
  143.      crc = crc_table[crch>>8] ^ (crcl<<8)
  144.  
  145. Substituting  this  relation into the algorithm  in  Fig.  1,  we
  146. easily obtain the algorithm in Fig. 2.
  147.  
  148.      That  much  having been said,  it only remains to  be  seen,
  149. whether  or not it has all been worthwhile.   How much faster  is
  150. table lookup?
  151.      After building a 128 byte sector filled with random numbers,
  152. I  ran  a  benchmark  in which the CRC  and  Checksum  were  each
  153. calculated 100 times with the following results.   Here each tick
  154. represents 1/60th of a second.
  155.  
  156. ________________________________________________________________
  157. ___Table.1: Comparison of methods for 100 sectors_______________
  158.  
  159. Slow CRC            120 ticks
  160. Table CRC            25 ticks
  161. Checksum              3 ticks
  162. ________________________________________________________________
  163.  
  164.      The table driven method is an order of magnitude faster than
  165. the older CRC method,  and only an order of magnitude slower than
  166. the Checksum method.   This offers a much smoother trade off than
  167. originally  available  with  the  CRC  check.    What  do   these
  168. differences mean in terms of effective through put?
  169.      My   communications   program   also  uses   the   following
  170. optimizations which can affect transfer speed:
  171.      All disk I/O is double buffered.
  172.      The  transmitter sends the body of the Xmodem  Packet  while
  173. simultaneously calculating the CRC.  This leads to an almost zero
  174. calculate time at low speeds.
  175.      The machine on the receiving end of the line only calculates
  176. the CRC after a complete packet has arrived.
  177. ________________________________________________________________
  178. ___Table.2: Transfer measurements_______________________________
  179.  
  180.                Effective Throughput: (bytes/sec)
  181.      Baud:     1200      2400      9600      19200     57600
  182. Method:        (128 byte packets)
  183. Slow CRC       106.......201.......598.......770.......773
  184. Table CRC      109.......210.......692.......1113......1172
  185. Checksum       110.......213.......709.......1155......1263
  186.  
  187. Method:        (1k byte packets)
  188. Slow CRC       ..........210.......628.......939.......994
  189. Table CRC      ..........220.......729.......1185......1185
  190. Checksum       ..........222.......745.......1226......1973
  191. ________________________________________________________________
  192.  
  193.      One  should take benchmarks with a grain of salt.   However,
  194. it  is clear that the table lookup algorithm stays closer to  the
  195. checksum  method  than the standard  bit  shift  algorithm.   The
  196. efficiency  and  speed  of compiled code can  vary  greatly  from
  197. machine  to  machine.   These tests were made with two  computers
  198. linked directly through their serial ports.
  199.      I have found that CompuServe typically yields and  effective
  200. throughput  of  60-80  bytes  per second  at  1200  baud.   Genie
  201. typically yields 70-80 bytes per second,  and my neighborhood Vax
  202. 785 lets me run with an effective throughput of 103-105 bytes per
  203. second, all with Xmodem.
  204.      In  my first attempt at Xmodem,  I used a function call  for
  205. processing each character in the crc loop.   In addition,  I  did
  206. not  overlap the CRC calculation with transmission of the packet.
  207. This  was  a  dreadful mistake.   I could not  get  an  effective
  208. throughput  of more than 500 characters per second even  with  4k
  209. buffers  at any speed.   The bottom line is that it take a number
  210. of optimizations to speed up a complex process.
  211.  
  212.